ISYE6501 Notes

Week 1

Module 1 - Intro & What is Modeling

What is modeling?

1. Describe a real-life situation mathematically
2. Analyze the math
3. Turn mathematical answer back into real-life situation

Can mean 3 things:

1. General (regression)
2. General with variables (regression using size, weight distance)
3. Specific estimates (regression using bias + coefficients * variables)

Module 2 - Classification

Error & cost:

• Minimizing errors: Classification lines try to divide data points with the max amount of distance to account for small data variations that might lead to classification errors.
• Should also consider weight of errors, between FPs and FNs. The more costly the error for either, the more distance we want to shift the line away from it. - Reflects "risk tolerance". Relevant in medical analytics.

Features:

• If you see a straight horizontal/vertical line between 2 features, it means that the feature parallel to the line is not useful.

Data Definitions

Tables

• Every row is a "data point"
• Each column of a data point contain "features", "attributes", "covariate", etc, ie. the X values.
• Response/outcome is the "answer" of each data point, ie. the y value.

Structured Data

• data stored in a structured way, either quantitatively (age) or categorically (gender, hair color)

Unstructured Data

• Data not easily described and stored.
• Example: Text

Common types of structured data

1. Quantitative - numbers with meaning
2. Categorical
   • Numbers without meaning (ex. zipcodes)
   • Non-numeric: Hair color
3. Binary data (subset of categorical data)
   • Can only take one of two values
   • Can sometimes be treated as a quantitative measure
4. Unrelated data - no relationship between data points
5. Time series data - same data recorded over time (stock, height of a child)
   • Often recorded at same interval (but not necessarily)

Support Vector Machines

Applied to credit loan problem:

m = number of data points
n = number of attributes
x_ij = jth attribute of ith data point
  x_i1 = credit score of person 1
  x_i2 = income of person i
y_i = response for data point i
  y_i = 1 (if data point i is blue, -1 if data point i is red)
line = (a_1 * x_1) + (a_2 * x_2) + (a_n * x_n) + a_0 = 0

Notes:

• Need to scale the data. If not, certain coefficients will be far more sensitive to change than others.
• If a certain coefficient (feature) is near-zero, it is probably not relevant for classification.
• Works the same in more dimensions (ie. more attributes)
• Classifier doesn't have to be a straight line. Can use kernel methods to make non-linear classifiers.
• Logistic regression is better for getting probability of classification (e.g. 37% likely to default).

Scaling data

Scaling linearly:

Scaling to a normal distribution:

Which method to use? Depends:

• Use scaling for data in a bounded range.
  • neural networks
  • optimization models that need bounded data
  • batting average (0.000-1.000)
  • RGB color intensities (0-255)
  • SAT scores (200-800)
• Use standardization for PCA / Clustering.
• Sometimes it won't be clear. Try both!

KNN Algorithm

Idea:

1. Find the class of a new data point
2. Pick the k-closest points ('nearest neighbors') to the new one
3. The new point's class is the most common among the k-neighbors

Things to keep in mind:

• Can be used for multi-class classification tasks.
• "K" is a parameter that can be tweaked.
• There is more than one way to calculate distance metrics.
• Some attributes can be weighted by importance.

Classification Summary

• Divides data points into groups based on similarity
• Graphical intuition
• Basic solution methods
  • SVM
  • KNN
• Data terminology
• Validation
• Distance metrics
• Confusion matrices

Week 2

Module 3 - Validation

Data has 2 types of patterns:

1. real effects - real relationship between attributes and response
2. random effect - random, but looks like a real effect

"Fitting" matches both:

• real effects: same in all data sets
• random effects: different in all data sets
• BUT: only real effects are duplicated in other data.

How to measure a model's performance:

• larger set of data to fit the model
• smaller set to measure the model's effectiveness

Train/Validate/Test to choose best model

What if we want to compare 5 runs of SVM and KNN?

Problems:

• Observed performance = real quality + random effects. High-performing models are more likely to have above-average random effects.
• Just choosing best performing model is too optimistic.

Solution:

• Use both validation and test data set.
• Training:Build, Validation:Pick, Test:Estimate performance

Splitting Data - Random/Rotation

How much data to use?

• Typically 70-90% training, 10-30% test.
• BUT to compare models: 50-70% train, split the rest equally between validation and test.

How to split data?

1. Random: Randomly sample split (60:20:20) without replacement.
2. Rotation: Take turns selecting points (e.g. 5 data point rotation sequence). Benefit: Equally separates data. Cons: May introduce bias, if rotations match a pattern (e.g. workdays)

Splitting Data - k-Fold Cross Validation

Idea: For each of the k parts - train the model on all the other parts and evaluate it on the one remaining.

• Pros: Better use of the data (trains across all available data), better estimate of model quality and more effective way to choose a model.
• For 4-fold, use 3 (ABC) for train, 1 (D) for test. Then rotate each fold to use as validation (see image). Essentially, each fold is used k-1 times for training, and 1 time for validation
• Finally, average the k evaluations to estimate the model's quality.
• Most common k is 10.
• Important: Don't use the resulting models from k-fold cross validation, either by choosing one of the trained model or averaging the coefficients across the k splits. Train the model again using all the data.

Module 4 - Clustering

Definition: Grouping data points

Use:

• Targeted marketing / market segmentation (market on size / price / versatility / aesthetics)
• Personalized medicine
• Locating facilities
• Image analysis (face recognition, captcha)
• Data investigation

Distance Norms

Euclidean (straight-line) distance

• 1-dimension $$ Distance = \sqrt(x_1-y_1)^2+(x_2-y_2)^2 = $$

Rectilinear distance

• 2-dimension
• Used for calculating distance in a grid.
• Also called "Manhattan distance"

$$ Distance = |x_1 - y_1| + |x_2 - y_2| $$

p-norm Distance (Minkowski Distance)

• n-dimension
• Sum over all n dimensions

$$ Distance = \sqrt[p]{\sum_{i=1}^{n}|x_i - y_i|^p} $$

Infinity Norms

• Definition: "The infinity norm simply measures how large the vector is by the magnitude of its largest entry." (reference)
• It is essentially p-norm distance where p is set to infinity.

$$ Distance = \sqrt{\sum_{i-1}^{n}|x_i - y_i|^{\infty}} = \sqrt[\infty]{\text{max}_i|x_i - y_i|^{\infty}} = max_i|x_i - y_i| $$

Why use infinity norms?

• Robotics example: Automated storage and retrieval system. Time it takes to store/retrieve depends on moving to the aisle (horizontal) and arm height (vertical).
• A "one-norm" would be the robot moving to the aisle, then lifting its arm to the correct height.
• An "infinity-norm" would be the robot moving + stretching its arms and the max time is dictated by whichever takes longer to complete.

K-Means Algorithm

How it works:

1. Pick k cluster centers within range of data
2. Assign each data point to nearest cluster center
3. These data points are not the actual "center" of the cluster. To find the center, recalculater cluster centers (centroids). These centroids are the new centroids.
4. After centroids are set, some data points might not be in the right cluster (determined by closeness to each centroid). Keep repeating steps 2 and 3 until there no more data point changes clusters.

Characteristics:

• k-means is a heuristic: Fast, good but not guaranteed to find the absolute best solution.
• Expectation-maximization - "Expectation" is the mean of a cluster's data point distance to the centroid. "Maximization" is the task - maximizing the negative to a cluster center.

K-means in practice

1. Outliers: k-means assigns whichever closest cluster to the outlier. Easiest way to solve is remove those outliers. But, best practice is to better understand why those outliers are there.
2. It's fast: Take advantage of its runtime by running several iterations.
   • For each run, choose a different initial cluster center (randomized initialization), then choose the best solution found.
   • Test different values of k as well.
3. Understanding k for optimization.
   • Make sure to "fit the situation you're analyzing". k == # of data points may be the most theoretically optimal, but does that actually make sense for the task?
   • Solution: Plot k vs total distance to find the "elbow" of the curve. At a certain number, the benefit of adding another k becomes negligible.

K-means for predictive clustering

Classification task: Given a new data point, determine which cluster set the new data point belongs to. To do this, simply put it into whichever cluster centroid it is closest to.

Another classification task: What range of possible data points would we assign to each cluster?

Image of cluster region, aka "Voronoi diagram"

Classification / Clustering - Differences

• Difference is what we know about the data points
• In classification, we know the correct classification of attributes. This is called supervised learning.
• In clustering, we don't know the correct classification of attributes. This is called unsupervised learning.

Week 3

Module 5 - Basic Data Preperation

Data Preparation: Quantitative Examples

• credit scores
• average daily temperature
• stock price

Things to watch out for before building models:

• Scale of the data: Can throw off models. Beware of possible outliers.
• Extraneous information: Complicates the model, harder to correctly interpret the solution.

Outlier Detection

Definition: Data point that's very different from the rest.

Types of outliers

• point outliers: values far from the rest of the data.
  • Example: Outlier point in a cluster scatterplot
• contextual outlier: value isn't far from the rest overall, but is far from points nearby in time.
  • Example: Time series data, low temperature at an unexpected time.
• collective outlier: Something is missing in a range of points, but can't tell exactly where.
  • Example: Missing hearbeat in a time series chart of ECG data.

How to detect outliers

1. Box-and-whisker plot

• helps find outliers (for 1D data)
• box is 25/75th percentile of values
• middle of the box is the median
• "whiskers" expanding outside of box is the reasonable range of values expected of the data (e.g. 10/90th or 5/95th percentile)
• Data points outside of the whisker could be considered outlier data.

2. Modeling error

• Idea: Fit model, then find points of high error
• Example: Fit exponential smoothing model to temperature/time series data.
• Points with very large error might be outlier. Model will expect smooth curve, but actual data is far from it.

Dealing with Outliers

Depends on the data:

• Bad data (failed sensor, bad experiment, bad input)... or maybe real data?
• Need to root cause - possible avenues: find data source, understand how it was compiled.
• With large data, outliers are expected.
  • In a normally-distributed data, 4% of data will be outside 2 standard deviations.
  • With 1,000,000 data points, >2000 expected outside 3 standard deviations.
  • Removing them can be too optimistic, account for noise.

Actions:

• If really bad data, remove the data, use data imputation
• If real/correct data, think whether the data you're modeling could realistically have outlier data points (e.g. force majeure incidents causing delays/cancellations).
• Modeling outliers: Using logistic regression model, estimate probability of outliers happening under different conditions. Then, use a second model to estimate length of delivery under normal conditions, using data without outliers.

Module 6 - Change Detection

Definition: Determining whether something has changed.

Why:

• Hypothesis tests often not sufficient for change detection, because they are slow to detect change.

Cumulative sum (CUSUM) approach

Definition: Detect increase/decrease or both by the cumulative sum.

How:

• The basic idea is to calculate a running total of the change $t-1$, where t is the number of time steps.
• If the running total is greater than zero we can keep it, otherwise the running total will reset to zero. This allows change to be detected quickly.
• The running total ($S_t$) can then be used as a metric to determine if it goes above a threshold $T$.
• $C$ is a buffer to pull the running down to prevent too many false positives from occurring.

Terms:

• $X_t$ = observed value at time $t$
• $\mu$ = mean of x, if no change
• $C$ = buffer value
• $T$ = threshold valued
• $X_t - \mu$ = how much above expected the observation is at time $t$
• $\mu - X_t$ = how much below expected the observation is at time $t$

Formula and Example:

Formula to detect increase (True if $S_t \ge T$)

$$ S_t = max{\left\{0, S_{t-1} + (X_t-\mu-C) \right\}} $$

Formula to detect decrease (True if $S_t \ge T$). $\mu$ and $X_t$ is flipped.

$$ S_t = max{\left\{0, S_{t-1} + (\mu-X_t-C) \right\}} $$

Note: Both can be used in conjunction to create a control chart, where $S_t$ is plotted over time and if it ever gets beyond this threshold line, it shows that CUSUM detected a change.

Week 4

Module 7 - Time Series Models

Exponential Smoothing

Time series data will have a degree of randomness. Exponential smoothing accounts for this by smoothing the curve.

Example:

• $S_t$ - expected baseline response a time period $t$
• $X_t$ - observed response at $t$
• What is real blood pressure over time without variation?
• Different blood pressure, increase in baseline, or random event?
• Ways to answer:
  • $S_t = X_t$ - observed blood pressure is real indicator
  • $S_t = S_{t-1}$ - today's baseline is the same as yesterday's baseline

Exponential Smoothing Model

• Sometimes called single, double, triple depending on how many aspects are considered (seasonality, trend)
• Triple exponential smoothing is also called Winter's Method or Holt-Winters.

Formula

$$ S_t = \alpha x_t + (1 - \alpha)S_{t-1} $$$$ 0 < \alpha < 1 $$

• $\alpha$ trades off between trusting $x_t$ when $\alpha$ is large, and trusting $S_{t-1}$ when $\alpha$ is small.
• $\alpha$ -> 0: A lot of randomness in the system.
  • Trust previous estimate $S_{t-1}$
• $\alpha$ -> 1: Not much randomness in the system.
  • Trust what you see $x_t$.
• How to start? Set initial condidation: $S_1 = x_1$
• Does not deal with trends or cyclical variations - more on that later.

Trends and Cycles in Exponential Smoothing

Time series complexities

• Trends (increase/decrease)
• Cyclical patterns (temp/sales/biometric cycles)

Trends

Exponential Smoothing, but with $T_t$ (trend at time period $t$): $$S_t = \alpha x_t + (1 - \alpha)(S_{t-1} + T_{t-1})$$

Trend at time $t$ based on delta between observed value $S_t$ and $S_{t-1}$ with a constat $\beta$. $$T_t = \beta (S_t - S_{t-1}) + (1-\beta)T_{t-1}$$

• Initial condition is $T_1 = 0$

Cyclic

Two ways to calculate:

1. Like trend - additive component of formula, or
2. Seasonalities: multiplicative way where:
   • $L$: Length of a cycle
     • e.g. $L=24$ for hourly reading of biometrics a day
   • $C_t$: Multiplicative seasonality factor for time $t$.
     • inflates/deflates the observation

Baseline formula (including trend + seasonality)

$$ S_t = \frac{\alpha x_t}{C_{t-L}} + (1 - \alpha)(S_{t-1} + T_{t-1}) $$

Update the seasonal (cyclic) factor in a similar way as trends:

$$C_t = \gamma(\frac{x_t}{S_t}) + (1 - \gamma)C_{t-L}$$

• No initial cyclic effect: $C_1$, ..., $C_L$ = 1

Example: Sales trends

• If $C$ is 1.1 on Sunday, then sales were 10% higher just because it was Sunday
• Of 550 sold on Sunday, 500 is baseline, 50 is 10% extra

Starting Conditions

For trend:

• $T_1 = 0$: No initial trend

For multiplicative seasonality

• Multiplying by 1: shows no initial cyclic effect
• First $L$ values of $C$ set to 1.

Exponential Smoothing: What the Name Means

"Smoothing"

• The equation smoothes high and low spikes using $\alpha$.
  • If we have high observed value $x_t$, the baseline estimate $S_t$ is not as high. High value is only weighted by $\alpha$ which is less than one, and pulled down from high point by previous baseline $S_{t-1}$.
  • If we have low observed value, $(1-\alpha)S_{t-1} term pulls the estimate up from the low observed value.

Graph of what it looks like:

"Exponential"

Each time period estimate can be plugged in like this:

• Each time period is weighted by $1-\alpha$ to an increasing exponent.
• Significance: Every past observations contributes to the current baseline estimate $S_t$.
• More recent observation are weighted more, i.e. more important.

Applications in Forecasting

Given basic exponential smoothing equation

$$S_t = \alpha x_t + (1-\alpha)S_{t-1}$$

We want to make a prediction $S_{t+1}$. Since $X_{t+1}$ is unknown, replace it with $S_t$.

Using $S_t$, the forecast for time period $t+1$ is

$$F_{t+1} = \alpha S_t + (1-\alpha)S_t$$

hence, our estimate is the same as our latest baseline estimate

$$F_{t+1} = S_t$$

Factoring in trend/cycle

Above equation can beextrapolated to trend/cycle calculations.

Best estimate of trend is the most current trend estimate:

$$F_{t+1} = S_t + T_t$$

Same for cycle (multiplicative seasonality)

$$F_{t+1} = (S_t + T_t) C_{(t+1)-L}$$

Where $F_t+k = (S_t + kT_t)C_{(t+1)-L+(k-1)}$, k=1,2,...

AutoRegressive Integrated Moving Average (ARIMA)

3 key parts

1. Differences

• Exponential smoothing assumes data is stationary, but reality is that it is not.
• However, the difference might be stationary.

• For example:

  • First-order difference $D_{(1)}$: difference of consecutive observations

  $$D_{(1)t} = (X_t - X_{t-1})$$

  • Second-order difference $D_{(2)}$: differences of the differences

  $$D_{(2)t} = (x_t - x_{t-1}) - (x_{t-1} - x_{t-2})$$

  • Third-order difference $D_{(3)}$: differences of the differences of the differences

  $$D_{(3)t} = [(x_t - x_{t-1}) - (x_{t-1} - x_{t-2})] - [(x_{t-1} - x_{t-2}) - (x_{t-2} - x_{t-3}]$$

  • The difference of differences = d times

2. Autoregression

Definition: Predicting the current value based on previous time periods' values.

Augoregression's exponential smoothing:

• order-$\infty$ autoregressive model.
• uses data all the way back.

Order-p autoregressive model:

• Go back only p time periods.

"ARIMA" combines autoregression and differencing

• autoregression on the differences
• use p time periods of previous observations to predict d-th order differences.

3. Moving Average

• Uses previous errors $\epsilon_t$ as predictors $$\epsilon_t = (\hat{x} - x_t)$$
• Apply order-q moving average (go back q time periods) $$\epsilon_{t-1}, \epsilon_{t-2}, \ldots , \epsilon_{t-q}$$

ARIMA (p,d,q) model

$$ D_{(d)t} = \mu + \sum_{i=1}^{p}\alpha_i D_{(d)t-i} - \sum_{i=1}^{q}\theta_i(\hat{x}_{t-1} - x_{t-i}) $$

Choose:

• p-th order autoregression
• d-th order difference
• q-th order moving average
• Once chosen, statistical software can be used to find the p, d, q constants through optimization.

Other flavors of ARIMA

• Add seasonal values of p, d, q
• Set specific values of p, d, q to get certain qualities
  • ARIMA(0,0,0) = white noise
  • ARIMA(0,1,0) = random walk
• Can generalize a lot of simpler models:
  • ARIMA(p,0,0) = AR (autoregressive) model
  • ARIMA(0,0,q) = MA (moving average) model
  • ARIMA(0,1,1) = basic exponential smoothing model
• Short-term forecasting
  • Usually better than exponential smoothing if:
  • Data is more stable, with fewer peaks/valleys/outliers.
• Need ~40 past data points for ARIMA to work well.

Generalized Autoregressive Conditional Heteroskedasticity (GARCH)

Definition: Estimate or forecast the variance of something, given a time-series data.

Motivation:

• Estimate the amount of error.
• Example: Forecast demand for pickup trucks
  • Variance tells how much forecast might be higher/lower than true value
• Example: Traditional portfolio optimization model.
  • Balances expected return of a portfolio with amount of volatility. (Risker: Higher expected return, vice-versa)
  • Variance is a proxy for the amount of volatility/risk.

Mathematical Model:

$$ \sum_t^2 = \omega + \Sigma_{i-1}^p\beta_i\sigma_{t-i}^2 + \sum_{i=1}^q \gamma_i\epsilon_{t-i}^2 $$

• Equation is similar to ARIMA, with 2 differences
  1. Uses variance/squared errors, not observations/linear errors.
  2. Uses raw variances, not differences of variances.
• Stat software can fit the model, given p and q (don't need d since GARCH doesn't use differences)

SUMMARY

1. Exponential smoothing
2. ARIMA - generalized version of exponential smoothing
3. GARCH - ARIMA-like model for analyzing variance

Week 5

Basic Regression

What it explains:

• Causation / Correlation
  • Value of a home run
  • Effect of economic factors on presidential election
• Prediction
  • Height of child at adulthood
  • Future oil price
  • Housing demand in next 6 months

Simple Linear Regression (SLR)

Definition: Linear regression with one predictor

• Looks for linear relationship between predictor and response.

Sum of Squared Error

Example:

• $y_i$ = cars sold for data point i
• $\hat{y}_i$ = model's prediction of cars sold
• Data point i's prediction error: $y_i - \hat{y}_i = y_i - (a_0 + a_1 x_{i1})$

Sum of Squared Errors $$ \sum_{i=1}^n(y_i - \hat{y}_i)^2 = \sum_{i=1}^n(y_i - (a_0 + a_1 x_{i1})^2 $$

Best-fit regression line

• line moves around the dimension to minimize sum of squared errors. As it moves, the values of the coefficients $a_0$ and $a_1$ change.
• Defined by $a_0$ and $a_1$

Maximum likelihood (or how to measure the quality of a model's fit)

• Likelihood: Measure the probability (density) for any parameter set.
• Maximum likelihood: Parameters that give the highest probability.

How it works:

• Assume that the observed data is the correct value and we have information about the variance.
• Then for any set of params we can measure the probability (density) that the model would generate the estimates it does.
• Whichever set of params that gives the highest probability density (ie. maximum likelihood). is the best-fit set of params.

Maximum Likelihood - Example

• Assumption: distributino of errors is normal with mean of zero and variance $\sigma^2$, and independently and identically distributed.
• Observation: $z_1$, ..., $z_n$
• Model estimates: $y_1$, ..., $y_n$
• Maximum-liklihood expection: The set of parameters that minimizes the sum of squared errors

MLE in Linear Regression

• $x_{ij}$ is the _j_th observed predicted value of data point $i$.
• $a_0$ through $a_m$ are the params we're trying to fit.

Maximum Likelihood Fitting

• Simple example: regression with independent normally distributed errors
• But can get complex with:
  • different estimation formulas
  • different assumptions about the error
• Stat software can handle most of these complexities.

Models that Combine Maximum Likelihood with Model Complexity

Akaike Information Criterion (AIC)

• $L^*$: Maximum likelihood value
• $k$: number of parameters being estimated

$$ AIC = 2k = 2\ln{(L^*)} $$

• $2k$ is the penalty term. Balances model's likelihood with its simplicity. This is done to reduce the chance of overfitting by adding too many parameters.
• Models with the smallest AIC is preferred.

AIC applied to regression

• $m+1$: number of parameters
• $L^*$ (max likelihood val) substitue: Linear regression function.

Corrected AIC ($AIC_c$)

• AIC weakness: Works well if there are infinitely many data points.
• Correct AIC accounts for this by adding a correction term.

Equation:

• $n$: Correction term

$$ AIC_c = AIC + \frac{2k(k+1)}{n-k-1} = 2k - 2\ln{(L^*)} + \frac{2k(k+1)}{n-k-1} $$

Comparing AIC / AICc models by Relative Probability

Example:

• Model 1: AIC = 75
• Model 2: AIC = 80

Relative likelihood $$ e^\frac{(AIC_1 - AIC_2)}{2} $$

Applied to Models 1 & 2: $$ e^\frac{(75 - 80)}{2} = 8.2\% $$

Result:

• Model 2 is 8.2.% as likely as Model 1 to be better.
• Considering lower AIC is better, Model 1 will be the better choice

Bayesian Information Criterion (BIC)

• $L^*$: Maximum likelihood value
• $k$: Number of parameters being estimated
• $n$: Number of data points

$$ BIC = k \ln{(n)} - 2 \ln{(L^*)} $$

Characteristics:

• Similar to AIC
• BIC's penalty term is greater than AIC.
• Encourage models with fewer params than AIC.
• Only use BIC when there are more data points than parameters

BIC Metrics - Rule of thumb

Summary of AIC / BIC

• AIC = Frequentist, BIC = Bayesian
• No hard-and-fast rule for using AIC or BIC or maximum likelihood.
• Looking at all three can help you decide which is best.